\vspace{-0.25in}
\section{Trees}
\vspace{-0.15in}
\label{sec:trees}

% 5 Nov: I don't think we actually need either of these lemmas anymore.
%Before we prove the general result, we need the following two lemmas, whose proofs are in the appendix. 

%\begin{lemma} 
%\label{lem:tree1}
%Let $X,Y$ be two independent random variables. Let $W = \min(X,Y)$. Then the pdf of $W$, $p(w) \leq p(x) + p(y)$.  
%\end{lemma} 


%\begin{lemma}
%\label{lem:tree2}
%Let $a_1,\ldots, a_d$ be a sequence of integers, with $\sum_i a_i = M$. Let $X$ and $Y$ be i.i.d random variables with distribution $\Pr(X = a_i) = \frac{1}{d}$. Then $E[\min(X,Y)] \leq \frac{M}{d}$. . 
%\end{lemma}


\begin{theorem}
\label{tree:main_result} 
For any tree, the expected cover time of a cobra-walk starting from any vertex is  $O(n \ln n)$. 
\end{theorem}

\junk{
It is also easy to see the following corollary for the line:
\begin{corollary}
Let L be a line graph of length $n$. The the expected cover time of $L$ is $O(n)$. 
\end{corollary} 
}

We will prove our main result by calculating the maximum hitting time
of a cobra-walk on a tree $T$ and then applying Matthew's
theorem. Cobra-walks on trees are especially tractable because they
follow two nice properties. Since a tree is a bipartite graph, this
means that pebbles in a cobra walk can't "leap over" one another and
we only need keep track of the pebble closes to the target. In
addition, the fact that there is one simple path between any two
vertices limits the number of collisions we need to keep track of, a
property which is not true for general graphs and makes cobra-walk
harder to analyze on them. For this section, we fix the branching
factor $k=2$. For $k>2$ but still constant, the cover time would not
be asymptotically better.

The general idea behind the proof is as follows. We take the longest
path w.r.t. hitting time in the tree. Along each vertex in this path,
except for the first and last, there will be a subtree rooted at that
vertex. If a cobra-walk's closest pebble to the endpoint is at vertex
$l$, the walk from this point can either advance with at least one
pebble, or it can not advance by either backtracking along the path,
going down the subtree rooted at $l$, or both. We show via a
stochastic dominance argument that a biased random walk from $l$,
whose transition probabilities are tuned to be identical to
cobra-walk's, will next advance to $l+1$ in a time that is dominated
primarily by the size of the subtree at $l$. This is done by analyzing
the return times in the non-advancement scenarios listed above. Thus
summing up over the entire walk, the hitting time is dominated by a
linear function of the size of the entire tree.

In Lemma \ref{tree:return} we bound the return time of a cobra-walk to
a root of the tree. \onlyShort{The proof can be found in the appendix and uses a
standard recursive technique.}

\begin{lemma}
\label{tree:return} 
Let $T$ be a tree of size $M$. Pick a root, $r$, and let $r$ have $d$
children. Then a cobra-walk on $T$ starting at $r$ will have a return
time to $r$ of $O(4M / d)$.
\end{lemma}

\onlyLong{
\begin{proof}

To show that the Lemma holds for a cobra-walk, we will actually show that it holds for a simple random walk with transition probabilities modified to resemble those of a cobra-walk. For this simple random walk, we start at $r$ and in the first step pick one of the children of $r, r'$. Let $(d'+1)$ be the degree of $r'$. Then we define transition probabilities as follows: $p$ is the probability of returning to $r$ in the next step, and $p$ is the probability of continuing down the tree. They are given as:
\begin{equation}
p = \left(1 - \left( \dfrac{d'}{(d' +1)} \right)^2 \right) , 
q =  \left( \dfrac{d'}{(d' +1)} \right)^2 ,
\frac{p}{q} = \frac{(d')^2}{(2d' + 1)} 
\end{equation}
Note that these are the exact same probabilities that a cobra walk at vertex $r'$ would have for sending (not sending) at least one (any) pebbles back to the root. . 

The rest of the proof follows by mathematical induction. Consider a tree $T$ that has only two levels. Starting from $r$, the return time, 2, is constant, the relationship holds. For the inductive case, assume that the hypothesis holds.  Then:
\begin{eqnarray}
r(T) & \leq & 1+ \sum_{r' \in N(r)} p(r')h_{r',r} 
\leq 1 + \frac{1}{d} \sum_{r' \in N(r)} h_{r',r} \\
&\leq& 1 + \frac{1}{d} \sum_{r' \in N(r)} \left(1 + \frac{d'^2}{2d' + 1} c \frac{|T'|}{d'}\right)
\leq 2 + \dfrac{c |T|}{2d} 
\end{eqnarray}
Setting $c = 4$ gives us the result of the lemma for the biased random walk, and it is easy to see that by stochastic dominance this holds also for the cobra walk. 
\end{proof}
}

Finally, we have a lemma for the hitting time of a single step of a path along a tree. 

\begin{lemma}
\label{tree:singlestep}
Fix a path in a tree $T$ made up of vertices $1,\ldots,l,l+1,\ldots,
t$.  Then, the expected time it takes for a cobra-walk starting at
vertex $l$ to get to $l+1$ with at least one pebble is given by:
\begin{equation}
h_{l,(l+1)}  = \frac{5}{4} + \frac{9}{5} \sum_{i = l}^{2} \left(\frac{1}{5}\right)^{l-i} |T_i|  
\end{equation}
where $T_l$ is the induced subtree formed by taking vertex $l$, its
neighbors not on the path being traversed, and all of their
descendants.
\end{lemma}

\onlyShort{The proof can be found in the appendix} Informally, we prove that the one-step hitting time is bounded by above by the worst case scenario that either both pebbles go back along the path or down the subtree rooted at $l$ and establish a simple recurrence relation.

\onlyLong{
\begin{proof}
Vertex $l$ is viewed through the context of having one edge to the vertex $l-1$, one edge to vertex $l$, and $d$ edges to some other vertices. Thus it can be viewed as the root of a tree,  and $T_l$ as the induced subgraph of $l$ and all vertices reached through its $d_l$ not-on-path children. We will need the following probabilities:
\begin{itemize}
\item  Probability of a pebble going from $l$ to $l+1 = p = \left(1 - \left(\dfrac{(d_l+1)}{(d_l+2)}\right)^2 \right)$
\item Probability of a pebble not going from $l$ to $l+1 = 1 - p = q$. 
\item Probability of a cobra walk sending both pebbles from $l$ to $l-1$ conditioned on it $not$ sending any pebbles from $l$ to $l+1 = q^{'}_l = \left(\dfrac{1}{(d_l+1)^2}\right)$ 
\item Probability of a cobra walk sending at least one pebble to the subtree $T_l$ conditioned on its not sending any pebbles to $l+1 = q^{''}_l = \left(\dfrac{(d_l)}{(d_l + 1)} \right)^2 + 2\left(\dfrac{d_l}{(d_l+1)^2}\right) = \dfrac{d_l^2 + 2d_l}{(d_l + 1)^2}$ 
\end{itemize}
Note that, conditioned on a pebble not advancing to vertex $l+1$, we actually have three disjoint events:  (A) Both pebbles go to $l-1$, (B) one pebble goes to $l-1$ and one pebble goes into subtree $T_l$, and (C) both pebbles go into $T_l$. We define an alternate event $B'$, which is the event that one pebble goes down $T_l$ and nothing else happens (thus, it is not technically in the space of cobra-walk actions). If we let $R$ be the  time until first return of the cobra-walk to $l$ conditioned on no pebble going to $l+1$, we wish to show that $E[R|B] \leq E[R|B']$ and that $E[R|C] \leq E[R|B']$. What is the relationship between $B$ and $B'$? Consider two random variables, $X$ and $Y$, and let $X$ be the time until first return of a pebble that travels from $l$ to $l-1$, $Y$ be the time until first return of a pebble that travels into $T_l$. Then $R|B$ is just another random variable, $U = \min(X,Y)$. Since $U \leq Y$ over the entire space, $E[U] \leq E[Y]$, and clearly $R|B'$ is equivalent to Y. Thus $E[R|B] \leq E[R|B']$ It is also easy to see that $E[R|B'] \geq E[R|C]$. Thus by the law of total expectation we have: 
\begin{eqnarray*}
E[R] &=& E[R|A]\Pr(A) + E[R|B]\Pr(B) + E[R|C]\Pr(C) \\
&\leq& E[R|A] \Pr(A)+ (\Pr(B) + \Pr(C))E[R|B'] \\
&=& E[R|A] \Pr(A) + E[R|B'](1 - \Pr(A)) 
\end{eqnarray*}

 Then the hitting time can be expressed as:  
\begin{eqnarray*}
h_{l,l+1} &\leq& p + q(E[R] + h_{l,l+1}) \\
\Rightarrow (1 - q) h_{l,l+1} &\leq& p + q(E[R]) \\
\Rightarrow h_{l,l+1} &\leq& 1 + \frac{q}{p} (q^{'}_l (1 + h_{l-1,l}) + q^{''}_l r(T_l)) 
\end{eqnarray*}
Note that $q/p = \frac{(d_l + 1)^2}{(2d_l + 3)}$. Since $r(T_l) \leq 4 |T_l| / d_l$ by Lemma \ref{tree:return}, we continue with:
\begin{eqnarray*}``
h_{l,l+1} &\leq& 1 + \frac{(d_l +1)^2}{(2d_l + 3)} \frac{1}{(d_l + 1)^2}(1 + h_{l-1,l}) +  \frac{(d_l +1)^2}{(2d_l + 3)} \frac{(d_l^2 + 2d_l)}{(d_l + 1)^2} \frac{4 |T_l|}{d_l} \\
&\leq& 1 + \frac{1}{5} (1 + h_{l-1,l}) + \frac{12}{5} |T_l|  
\end{eqnarray*}


If we expand the relation, we get:
\begin{eqnarray*}
h_{l,l+1} &\leq& \sum_{i = 0}^{l} \left(\frac{1}{5}\right)^i + \frac{12}{5} \left( |T_l| +  \left(\frac{1}{5}\right) |T_{l-1}| + \left(\frac{1}{5}\right)^2 |T_{l-2}| + \dots + \left(\frac{1}{5}\right)^{l-2} |T_{2}|\right) \\
h_{l,(l+1)} & \leq& \frac{5}{4} + \frac{12}{5} \sum_{i = l}^{2} \left(\frac{1}{5}\right)^{l-i} |T_i|  
\end{eqnarray*}
\end{proof}

}

We are finally ready to prove our main results for tree, Theorem~\ref{tree:main_result}, that the cobra-walk cover time of an arbitrary tree occurs in $O(n \ln n)$ steps. 

\begin{proof}
By Matthew's Theorem for cobra-walks, $C(G) \leq (\ln n + o(1)) h_{max}$. We just need to prove that $h_{max}$ occurs in linear time.

Let $P$ be the path for which $h_{u,v}$ is maximized, and let the path consist of the sequence of vertices $1,2,\ldots,t$. As in the proof of the single-step hitting time, we note that for all but the first and last vertices on $P$, there is a subtree $T_l$ of size $|T_l|$ rooted at each vertex. Because $h_{1,l} \leq h_{1,2} + h_{2,3} + \ldots h_{t-1,t}$. Then, we obtain the desired result from Lemma \ref{tree:singlestep} as follows:
\begin{equation}
h_{1,t} \leq \frac{5}{4} t + \frac{12}{5} \sum_{j = 2}^{t-1}  \left[ |T_j| \sum_{i = 0}^{\infty} \left(\frac{1}{5}\right)^i \right] 
\leq \frac{5}{4} t + \frac{12}{5} \frac{5}{4}  \sum_{j=2}^{t-1} |T_j| \leq 4 n 
\end{equation} 
\end{proof}


